翻訳と辞書 |
Matroid partitioning : ウィキペディア英語版 | Matroid partitioning The matroid partitioning problem is a problem arising in the mathematical study of matroids and in the design and analysis of algorithms, in which the goal is to partition the elements of a matroid into as few independent sets as possible. An example is the problem of computing the arboricity of an undirected graph, the minimum number of forests needed to cover all of its edges. Matroid partitioning may be solved in polynomial time, given an independence oracle for the matroid. It may be generalized to show that a matroid sum is itself a matroid, to provide an algorithm for computing ranks and independent sets in matroid sums, and to compute the largest common independent set in the intersection of two given matroids.〔.〕 ==Example==
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned, or equivalently (by adding overlapping edges to each forest as necessary) the minimum number of spanning forests whose union is the whole graph. A formula proved by Crispin Nash-Williams characterizes the arboricity exactly: it is the maximum, over all subgraphs of the given graph , of the quantity .〔.〕 The forests of a graph form the independent sets of the associated graphic matroid, and the quantity appearing in Nash-Williams' formula is the rank of the graphic matroid of , the maximum size of one of its independent sets. Thus, the problem of determining the arboricity of a graph is exactly the matroid partitioning problem for the graphic matroid. The fact that the elements of this matroid cannot be partitioned into fewer than independent subsets is then just an application of the pigeonhole principle saying that, if items are partitioned into sets of size at most , then at least sets are needed. The harder direction of Nash-Williams' formula, which can be generalized to all matroids, is the proof that a partition of this size always exists.〔
抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「Matroid partitioning」の詳細全文を読む
スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|